THE BELLMAN-FORD ALGORITHM AND “DISTRIBUTED BELLMAN-FORD”

In the spring of 2003, I began to wonder about the history of the Bellman-Ford algorithm [CLRS01] for finding shortest paths in a graph. In particular, I was interested in understanding when Bellman’s name and Ford’s name became jointly associated with the algorithm. To research these questions, I made trips to the BBN Technologies and MIT libraries, did Web searches, and sent emails to university professors who taught courses or wrote books on algorithms, parallel processing, or routing in networks. I didn’t find the source of the joint name in the several weeks before I grew tired of searching the massive literature on shortest path algorithms. 1 However, I did learn a good bit, as described below. Two highly regarded books give some history of the algorithm. Lawler [Law76] introduces “Bellman’s equations, ” and the Bellman-Ford method, referring to Ford’s 1956 RAND note [For56] and Bellman’s 1958 paper [Bel58]. He also cites Moore’s 1957 [Moo59] paper, saying the Moore’s method is more like Dijkstra’s [Dij59]. Tarjan [Tar83] introduces Ford’s “labeling method ” [For56], and then a breadthfirst method based on the independent ideas of Bellman [Bel58] and Moore [Moo59]. He doesn’t appear to give a name to what he describes. Deo and Pang’s large bibliography [DP84] also points to these three papers, saying, “Algorithms that solve the single-source problem are usually based on th